Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Tree View Pattern (medium)
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Comparison of Two Trees Pattern (medium)
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Mirror Image Trees

Problem Statement

Given two binary trees root and root2, return true if they are mirror images of each other. Otherwise, return false.

Two trees are said to be mirror images if, for every node in one tree, there is a corresponding node in the other tree with a mirrored structure. This means the left subtree of one tree is a mirror reflection of the right subtree of the other tree, and vice versa.

Examples

Example 1

  • Input: root1 = [1,2,3,4,null,null,5], root2 = [1,3,2,5,null,null,4]
Image
  • Expected Output: true
  • Justification: Both trees have the same root, and the left and right subtrees are mirrors of each other.

Example 2

  • Input: root1 = [4, 5, 6, null, 7], root2 = [4, 6, 5, null, null, 7]
Image
  • Expected Output: true
  • Justification: Both trees are a mirror of each other.

Example 3

  • Input: root1 = [1, 2, null, 3], root2 = [1, null, 2]
Image
  • Expected Output: false
  • Justification: The structure of the subtrees differs. The first tree contains node 3 but the second tree doesn't.

Solution

To solve this problem, we will use the Breadth-First Search (BFS) approach, which allows us to traverse both binary trees level by level. We maintain two queues to compare the nodes of both trees at each level in a mirrored manner. We add the left child of the first tree and the right child of the second tree to their respective queues, and vice versa. This way, the algorithm checks for symmetry at every level. If at any point, we find that the node values or their structures differ, we return false. If both queues are empty at the end of traversal, the trees are mirrors, and we return true.

The BFS approach is well-suited for this problem because it ensures that we process all nodes in a controlled manner. By utilizing two queues, we can efficiently compare nodes without recursion, which prevents stack overflow issues for deep trees. This method ensures that both trees are checked for symmetry in a straightforward, iterative manner, making it both effective and space-efficient.

Step-by-Step Algorithm

  1. Initial Check:

    • If both trees are empty (root1 == null and root2 == null), return true since two empty trees are considered mirrors.
    • If one tree is empty while the other is not, return false, as they cannot be mirrors.
  2. Queue Initialization:

    • Initialize two queues: queue1 and queue2.
    • Enqueue the root of the first tree into queue1 and the root of the second tree into queue2.
  3. Traversal Loop:

    • While both queues are not empty:
      • Dequeue the front of both queues (node1 from queue1 and node2 from queue2).
      • Value Check:
        • If the value of node1 is not equal to node2, return false.
      • Left and Right Child Check:
        • For the left child of node1 and the right child of node2:
          • If both are not null, enqueue node1.left to queue1 and node2.right to queue2.
          • If one is null and the other is not, return false.
        • For the right child of node1 and the left child of node2:
          • If both are not null, enqueue node1.right to queue1 and node2.left to queue2.
          • If one is null and the other is not, return false.
  4. Completion:

    • After the traversal loop, check if both queues are empty.
    • If both are empty, return true (the trees are mirrors). Otherwise, return false.

Algorithm Walkthrough

Input: root1 = [1,2,3,4,null,null,5], root2 = [1,3,2,5,null,null,4]

Image
  1. Initial Check:

    • Both root1 and root2 are not null, so we proceed.
  2. Queue Initialization:

    • Enqueue root1 (value 1) into queue1.
    • Enqueue root2 (value 1) into queue2.
  3. First Iteration:

    • Dequeue queue1 → node1 = 1.
    • Dequeue queue2 → node2 = 1.
    • Value Check: node1.val == node2.val (1 == 1), so continue.
    • Left and Right Child Check:
      • node1.left = 2 and node2.right = 2: Both are not null, so enqueue 2 to queue1 and 2 to queue2.
      • node1.right = 3 and node2.left = 3: Both are not null, so enqueue 3 to queue1 and 3 to queue2.
  4. Second Iteration:

    • Dequeue queue1 → node1 = 2.
    • Dequeue queue2 → node2 = 2.
    • Value Check: node1.val == node2.val (2 == 2), so continue.
    • Left and Right Child Check:
      • node1.left = 4 and node2.right = 4: Both are not null, so enqueue 4 to queue1 and 4 to queue2.
      • node1.right = null and node2.left = null: Both are null, so continue.
  5. Third Iteration:

    • Dequeue queue1 → node1 = 3.
    • Dequeue queue2 → node2 = 3.
    • Value Check: node1.val == node2.val (3 == 3), so continue.
    • Left and Right Child Check:
      • node1.left = null and node2.right = null: Both are null, so continue.
      • node1.right = 5 and node2.left = 5: Both are not null, so enqueue 5 to queue1 and 5 to queue2.
  6. Fourth Iteration:

    • Dequeue queue1 → node1 = 4.
    • Dequeue queue2 → node2 = 4.
    • Value Check: node1.val == node2.val (4 == 4), so continue.
    • Left and Right Child Check:
      • node1.left = null and node2.right = null: Both are null, so continue.
      • node1.right = null and node2.left = null: Both are null, so continue.
  7. Fifth Iteration:

    • Dequeue queue1 → node1 = 5.
    • Dequeue queue2 → node2 = 5.
    • Value Check: node1.val == node2.val (5 == 5), so continue.
    • Left and Right Child Check:
      • node1.left = null and node2.right = null: Both are null, so continue.
      • node1.right = null and node2.left = null: Both are null, so continue.
  8. Completion:

    • Both queue1 and queue2 are now empty, meaning the trees are mirror images. Return true.

Code

Java

. . . .

Complexity Analysis

Time Complexity

  • In the worst-case scenario, both trees will have n nodes (where n is the number of nodes in either tree).
  • During the BFS traversal, every node in both trees is visited exactly once. For each node, we perform constant-time operations (checking if values match, enqueueing children, etc.).
  • Hence, the overall time complexity is , where n is the number of nodes in the trees.

Space Complexity

  • The space complexity is determined by the maximum size of the queue. In the worst-case scenario, both trees are balanced, and the queue can hold at most nodes at a given time (since we are storing nodes of both trees in queues).
  • Therefore, the space complexity is .
Mirror Image Trees (medium)
Subtree of Another Tree (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity